
// 二叉树的最大深度
// 方法一：遍历二叉树求得答案-用外部变量记录每个节点的深度，取最大值即可

int res = 0; // 记录最大深度

int depth = 0; // 记录遍历到的节点的深度

// 主函数
int maxDepth(TreeNode* root)
{
        traverse(root);void traverse(TreeNode* root)
{
	if(root == nullptr)
		return;

	// 前序位置
	traverse(root->left);

	// 中序位置
	tarverse(root->right);

	// 后序位置
}


// 二叉树的最大深度
// 方法一：遍历二叉树求得答案-用外部变量记录每个节点的深度，取最大值即可

int res = 0; // 记录最大深度

int depth = 0; // 记录遍历到的节点的深度

// 主函数
int maxDepth(TreeNode* root)
{
	traverse(root);
	return res;
}

// 二叉树遍历框架
void traverse(TreeNode* root)
{
	if(root == nullptr)
		return;

	// 前序位置 - 前序位置是进入一个节点的时候
	depth++;

	if(root->left == nullptr || root->right == nullptr)
		res = max(res, depth); // 到达叶子节点，更新最大深度
	
	traverse(root->left);
	traverse(root->right);

	// 后序位置 - 后序位置是离开一个节点的时候
	depth--;
}


// 二叉树的最大深度 - 遍历解法
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        traverse(root); // 遍历当前二叉树

        return res;
    }

private:
    // 记录最大深度
    int res = 0;

    // 记录当前节点的深度
    int depth = 0;

    // 遍历二叉树
    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        depth++; //    前序位置 - 进入一个节点之前

        if(root->left == nullptr && root->right == nullptr) // 到达叶子节点
        {
            res = max(res, depth);
        }

        traverse(root->left);
        traverse(root->right);

        depth--; // 后序位置 - 离开一个节点之后
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        traverse(root);

        return res;
    }

private:
    // 记录最大深度
    int res = 0;

    // 记录当前节点的深度
    int depth = 0;

    // 遍历二叉树
    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 前序位置 - 进入一个节点之前
        depth++;

        // if(root->left == nullptr && root->right == nullptr)
        // {
        //     // 到达叶子节点，更新最大深度
        //     res = max(res, depth);
        // }

        res = max(res, depth); // 这样也可以

        traverse(root->left);
        traverse(root->right);

        // 后序位置 - 离开一个节点之后
        depth--;
    }
};


// 分解子问题
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        if(root == nullptr) 
            return 0;

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        // 左右子树的深度最大值+1即可得到二叉树的最大深度
        int res = max(leftDepth, rightDepth) + 1; // +1是根节点自己

        return res;
    }
};



// 二叉树的前序边流 - 分解问题 - 这种方法很妙 - 可以锻炼对于容器的基本使用
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        // 分解子问题：根节点+左子树前序遍历+右子树前序遍历

        vector<int> res;

        if(root == nullptr)
            return res;

        // 前序位置 - 进入一个节点之前
        res.push_back(root->val);

        vector<int> leftNum = preorderTraversal(root->left);
        res.insert(res.end(), leftNum.begin(), leftNum.end());

        vector<int> rightNum = preorderTraversal(root->right);
        res.insert(res.end(), rightNum.begin(), rightNum.end());

        return res;
    }
};



// 二叉树的直径
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) 
    {
        // 二叉树直径 - 一个节点的左右子树的最大深度之和

        maxDepth(root);

        return maxDiameter;
    }

private:
    int maxDiameter = 0;

    int maxDepth(TreeNode* root)
    {
        if(root == nullptr)
            return 0;

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        // 后序位置

        int myDiameter = leftDepth + rightDepth;

        maxDiameter = max(maxDiameter, myDiameter);

        return max(leftDepth, rightDepth) + 1;
    }
};



// 剑指offer-二叉树剪枝
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) 
    {
        if(root == nullptr)
            return nullptr;

        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);

        // 后序遍历位置，判断自己是否是值为0的叶子节点

        if(root->val == 0 && root->left == nullptr && root->right == nullptr)
            return nullptr; // 返回值会被父节点接受，相当于自己被删除掉了

        return root; // 如果不是，正常返回
    }
};


// 删除给定值的叶子节点
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) 
    {
        if(root == nullptr) 
            return nullptr;

        root->left = removeLeafNodes(root->left, target);
        root->right = removeLeafNodes(root->right, target);

        if(root->val == target && root->left == nullptr && root->right == nullptr)
            return nullptr;

        return root;
    }
};



// 翻转二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root == nullptr)
            return nullptr;

        // 先反转左右子树
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);

        // 然后交换左右节点
        root->left = right;
        root->right = left;

        return root;
        
    }
};


// 翻转二叉树 - 遍历二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        // 遍历二叉树
        traverse(root);

        return root;
    }

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;

        traverse(root->left);

        traverse(root->right);
    }
};



// 剑指offer-二叉树的镜像
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) 
    {
        // if(root == nullptr)
        //     return nullptr;

        // TreeNode* left = mirrorTree(root->left);
        // TreeNode* right = mirrorTree(root->right);

        // root->left = right;
        // root->right = left;

        // return root;

        traverse(root);

        return root;
    }

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;

        traverse(root->left);
        traverse(root->right);
    }
};


// 填充每个节点的下一个右侧节点指针
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) 
    {
        if(root == nullptr)
            return nullptr;

        // 遍历 三叉树，连接相邻节点
        traverse(root->left, root->right);

        return root;    
    }

    // 三叉树遍历框架
    void traverse(Node* node1, Node* node2)
    {
        if(node1 == nullptr || node2 == nullptr)
            return;

        // 前序遍历位置
        // 将传入的两个节点串起来
        node1->next = node2;

        // 连接相同父节点的两个子节点
        traverse(node1->left, node1->right);
        traverse(node2->left, node2->right);

        // 链接跨越父节点的两个子节点
        traverse(node1->right, node2->left);
    }
};


// 二叉树展开为链表
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) 
    {
        // 1. 将 root 的左子树和右子树拉平
        // 2. 将 root 的右子树接到左子树下方，然后将整颗左子树作为右子树
        // base case
        if(root == nullptr)
            return;

        // 先递归拉平左右子树
        flatten(root->left);
        flatten(root->right);

        // 后序遍历位置
        // 1. 左右子树已经被拉平成一条链表
        TreeNode* left = root->left;
        TreeNode* right = root->right;

        // 2. 将左子树作为右子树
        root->left = nullptr;
        root->right = left;

        // 3. 将原先的右子树接到当前右子树的末端
        TreeNode* p = root;
        while(p->right != nullptr)
        {
            p = p->right;
        }

        p->right = right;
    }
};



/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) 
    {
        if(root == nullptr)
            return nullptr;

        // 遍历三叉树，连接相邻节点
        traverse(root->left, root->right);

        return root;    
    }

    void traverse(Node* node1, Node* node2)
    {
        if(node1 == nullptr || node2 == nullptr)
            return;

        node1->next = node2;

        traverse(node1->left, node1->right);
        traverse(node2->left, node2->right);

        traverse(node1->right, node2->left);
    }
};




// 二叉树的中序遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        // 递归分解子问题
        vector<int> res;

        if(root == nullptr)
            return res;

        vector<int> leftNum = inorderTraversal(root->left);
        res.insert(res.end(), leftNum.begin(), leftNum.end());

        res.push_back(root->val);

        vector<int> rightNum = inorderTraversal(root->right);
        res.insert(res.end(), rightNum.begin(), rightNum.end());

        return res;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        // 递归分解子问题

        // base case
        if(root == nullptr)
            return 0;

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        
        return max(leftDepth, rightDepth) + 1;
    }
};



// 最大二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) 
    {
        return build(nums, 0, nums.size() - 1);
    }

    TreeNode* build(vector<int>& nums, int left, int right)
    {
        // base case 
        if(left > right)
            return nullptr;

        int index = -1, maxNum = INT_MIN;

        for(int i = left; i <= right; i++)
        {
            if(maxNum < nums[i])
            {
                index = i;
                maxNum = nums[i];
            }
        }

        // 构建根节点
        TreeNode* root = new TreeNode(maxNum);

        // 构建左右子树
        root->left = build(nums, left, index - 1);
        root->right = build(nums, index + 1, right);

        return root;
    }
};


// 最大二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) 
    {
        return build(nums, 0, nums.size() - 1);
    }

    TreeNode* build(vector<int>& nums, int left, int right)
    {
        // base case
        if(left > right)
            return nullptr;

        int index = -1, maxNum = INT_MIN;

        for(int i = left; i <= right; i++)
        {
            if(maxNum < nums[i])
            {
                index = i;
                maxNum = nums[i];
            }
        }

        // 构建根节点
        TreeNode* root = new TreeNode(maxNum);

        // 构建左右子树
        root->left = build(nums, left, index - 1);
        root->right = build(nums, index + 1, right);

        return root;
    }
};


// 从前序与中序遍历序列构建二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {

private:
    // 存储inorder中节点值到索引的映射-该题节点值是不重复的,可以使用unordered_map,降低时复
    unordered_map<int, int> valToIndex;

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        for(int i = 0; i < inorder.size(); i++)
        {
            valToIndex[inorder[i]] = i;
        }

        return build(preorder, 0, preorder.size() - 1,
                     inorder, 0, inorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                    vector<int>& inorder, int inStart, int inEnd)
    {   
        if(preStart > preEnd)
            return nullptr;

        int rootVal = preorder[preStart];
        int index = valToIndex[rootVal];

        int leftSize = index - inStart; // 左子树长度

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize,
                           inorder, inStart, index - 1);

        root->right = build(preorder, preStart + leftSize + 1, preEnd,
                            inorder, index + 1, inEnd);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {

private:
    // 构建inorder节点值到索引的映射
    unordered_map<int, int> valToIndex;

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        for(int i = 0; i < inorder.size(); i++)
        {
            valToIndex[inorder[i]] = i;
        }

        return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                    vector<int>& inorder, int inStart, int inEnd)
    {
        // base case
        if(preStart > preEnd)
            return nullptr;

        int rootVal = preorder[preStart];
        int index = valToIndex[rootVal];

        int leftSize = index - inStart; // 左子树的长度

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize,
                           inorder, inStart, index - 1);
        root->right = build(preorder, preStart + leftSize + 1, preEnd,
                            inorder, index + 1, inEnd);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {

private:
    // 建立inorder节点值到索引的映射
    unordered_map<int, int> valToIndex;

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        for(int i = 0; i < inorder.size(); i++)
        {
            valToIndex[inorder[i]] = i;
        }

        return build(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
    }

    TreeNode* build(vector<int>& inorder, int inStart, int inEnd,
                    vector<int>& postorder, int postStart, int postEnd)
    {
        // base case
        if(inStart > inEnd)
            return nullptr;

        int rootVal = postorder[postEnd];
        int index = valToIndex[rootVal];

        int leftSize = index - inStart; // 左子树的长度

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(inorder, inStart, index - 1,
                           postorder, postStart, postStart + leftSize - 1);

        root->right = build(inorder, index + 1, inEnd,
                            postorder, postStart + leftSize, postEnd - 1);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) 
    {
        return build(nums, 0, nums.size() - 1);
    }

    TreeNode* build(vector<int>& nums, int left, int right)
    {
        // base case
        if(left > right)
        {
            return nullptr;
        }

        int maxVal = INT_MIN, index = -1;

        for(int i = left; i <= right; i++)
        {
            if(maxVal < nums[i])
            {
                index = i;
                maxVal = nums[i];
            }
        }

        // 构建根节点
        TreeNode* root = new TreeNode(maxVal);

        // 构建左右子树
        root->left = build(nums, left, index - 1);
        root->right = build(nums, index + 1, right);

        return root;

    }
};


// 剑指offer-重建二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {

private:
    // 建立中序序列值到索引的映射
    unordered_map<int, int> valToIndex;

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        // 根据 前序遍历 确定根节点，根据 中序遍历 确定左右子树
        
        for(int i = 0; i < inorder.size(); i++)
        {
            valToIndex[inorder[i]] = i;
        }

        return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& inorder, int inStart, int inEnd)
    {
        // base case
        if(preStart > preEnd)
        {
            return nullptr;
        }

        int rootVal = preorder[preStart];
        int index = valToIndex[rootVal];

        // 左子树大小 - 只有知道了左子树大小，才能找到前序序列的右子树
        int leftSize = index - inStart;

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize, 
                           inorder, inStart, index - 1);
        root->right = build(preorder, preStart + leftSize + 1, preEnd, 
                            inorder, index + 1, inEnd);

        return root;
    }
};



// 从前序与中序遍历序列构建二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {

private:
    // 建立 中序序列 值到索引的映射
    unordered_map<int, int> valToIndex; 

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        for(int i = 0; i < inorder.size(); i++)
        {
            valToIndex[inorder[i]] = i;
        }

        return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& inorder, int inStart, int inEnd)
    {
        // base case
        if(preStart > preEnd)
            return nullptr;

        int rootVal = preorder[preStart];
        int index = valToIndex[rootVal];

        int leftSize = index - inStart; // 左子树的大小

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize, 
                           inorder, inStart, index - 1);
        root->right = build(preorder, preStart + leftSize + 1, preEnd, 
                            inorder, index + 1, inEnd);

        return root;
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {

private:
    // 构建中序序列值到索引的映射
    unordered_map<int, int> valToIndex;

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        for(int i = 0; i < inorder.size(); i++)
        {
            valToIndex[inorder[i]] = i;
        }

        return build(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
    }

    TreeNode* build(vector<int>& inorder, int inStart, int inEnd, 
                    vector<int>& postorder, int postStart, int postEnd)
    {
        // base case
        if(inStart > inEnd)
            return nullptr;

        int rootVal = postorder[postEnd];
        int index = valToIndex[rootVal];

        int leftSize = index - inStart;

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(inorder, inStart, index - 1, 
                           postorder, postStart, postStart + leftSize - 1);
        root->right = build(inorder, index + 1, inEnd, 
                            postorder, postStart + leftSize, postEnd - 1);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) 
    {
        // 二叉树直径 - 一个节点左右子树最大深度之和

        maxDepth(root);

        return maxDiameter;
    }

private:
    int maxDiameter = 0; // 最大直径

    int maxDepth(TreeNode* root)
    {
        // base case
        if(root == nullptr)
            return 0;

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        // 后序遍历位置
        int myDiameter = leftDepth + rightDepth;

        maxDiameter = max(maxDiameter, myDiameter);

        return max(leftDepth, rightDepth) + 1;
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        // 方法一：遍历二叉树
        traverse(root);

        return res;
    }

private:
    int res = 0;

    int depth = 0; // 当前节点的深度

    void traverse(TreeNode* root)
    {
        // base case
        if(root == nullptr)
            return;

        // 前序遍历位置
        depth++;

        if(root->left == nullptr && root->right == nullptr)
            res = max(res, depth);

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        depth--;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        // 方法二：递归分解子问题
        
        // base case
        if(root == nullptr)
            return 0;

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        int ret = max(leftDepth, rightDepth) + 1;

        return ret;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {

private:
    // 建立后序遍历值到索引的映射
    unordered_map<int, int> valToIndex;

public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) 
    {
        for(int i = 0; i < postorder.size(); i++)
        {
            valToIndex[postorder[i]] = i;
        }

        return build(preorder, 0, preorder.size() - 1, 
                     postorder, 0, postorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& postorder, int postStart, int postEnd)
    {
        // base case
        if(preStart > preEnd)
            return nullptr;

        if(preStart == preEnd)
            return new TreeNode(preorder[preStart]); // ???

        int rootVal = preorder[preStart];
        int leftRootVal = preorder[preStart + 1];

        // 通过前序序列左子树根节点可以确定后序序列左右子树区间
        int index = valToIndex[leftRootVal];

        int leftSize = index - postStart + 1; // 左子树大小

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize, 
                           postorder, postStart, index);
        root->right = build(preorder, preStart + leftSize + 1, preEnd, 
                            postorder, index + 1, postEnd - 1);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {

private:
    // 记录每棵子树的出现次数
    unordered_map<string, int> memo;

    // 记录结果
    vector<TreeNode*> res;

public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) 
    {
        traverse(root);

        return res;
    }

    string traverse(TreeNode* root)
    {
        // base case
        if(root == nullptr)
            return "#";

        string left = traverse(root->left);
        string right = traverse(root->right);

        // 后序遍历位置
        string s = left + ',' + right + ',' + to_string(root->val);

        int sum = memo[s];

        // 多次重复也只会被加入结果集一次
        if(sum == 1)
            res.push_back(root);

        // 给子树对应的位置+1
        memo[s] = sum + 1;

        return s;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

private:
    vector<string> path; // 记录tarverse函数递归时的路径

    vector<string> ret; // 记录从根节点到叶子节点的路径

    void traverse(TreeNode* root)
    {
        // base case
        if(root == nullptr)
            return;

        // 叶子节点
        if(root->left == nullptr && root->right == nullptr)
        {
            path.push_back(to_string(root->val));
            ret.push_back(join("->", path));
            path.pop_back();
            return;
        }

        // 前序遍历位置
        path.push_back(to_string(root->val));

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }

    string join(const string& sep, const vector<string>& path)
    {
        string res = "";
        for(int i = 0; i < path.size(); i++)
        {
            res += path[i];
            if(i < path.size() - 1)
                res += sep;
        }

        return res;
    }

};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    string path;

    int ret = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 前序遍历位置
        path += to_string(root->val);

        if(root->left == nullptr && root->right == nullptr)
            ret += stoi(path);

        traverse(root->left);
        traverse(root->right);

        path.pop_back();
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    vector<int> ret;

    int depth = 0; // 记录递归的层数

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 前序遍历位置
        depth++;

        if(ret.size() < depth)
        {
            // 这一层还没有记录值
            // 说明 root 就是右侧视图的第一个节点
            ret.push_back(root->val);
        }

        // 这里反过来，先遍历右子树再遍历左子树
        // 这样首先遍历的一定是右侧节点
        traverse(root->right);
        traverse(root->left);

        // 后序遍历位置
        depth--;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    vector<int> ret;

    int depth = 0; // 递归层数

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 前序遍历位置
        depth++;

        if(ret.size() < depth)
        {
            // 说明这一层还没有记录值
            // 此时的root节点就是右侧节点
            ret.push_back(root->val);
        }

        traverse(root->right);
        traverse(root->left);

        // 后序遍历位置
        depth--;

    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int longestConsecutive(TreeNode* root) 
    {
        traverse(root, 1, INT_MIN);

        return maxLen;
    }

    int maxLen = 0;

    void traverse(TreeNode* root, int len, int parentVal)
    {
        if(root == nullptr)
            return;

        if(root->val == parentVal + 1)
            len++;
        else 
            len = 1;
        
        maxLen = max(maxLen, len);

        traverse(root->left, len, root->val);
        traverse(root->right, len, root->val);
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string smallestFromLeaf(TreeNode* root) 
    {
        traverse(root);

        return res;
    }

    // 递归遍历过程中的路径
    string path;

    // 结果字符串
    string res = "";

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 叶子节点，更新结果
        if(root->left == nullptr && root->right == nullptr)
        {
            path += (char)('a' + root->val);
            // 需要反转字符串比较结果
            reverse(path.begin(), path.end());

            if(res.empty() || res.compare(path) > 0)
                res = path;

            // 还原字符串
            reverse(path.begin(), path.end());
            path.pop_back();
            return;
        }

        // 前序遍历位置
        path += (char)('a' + root->val);

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    // 记录根节点到叶子节点的二进制数
    int path = 0;

    // 记录结果
    int ret = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，记录结果
        if(root->left == nullptr && root->right == nullptr)
        {
            ret += path << 1 | root->val;

            return;
        }

        // 前序遍历位置
        path = path << 1 | root->val;

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path = path >> 1;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    // 记录根节点到叶子节点的二进制数
    int path = 0;

    // 记录结果
    int ret = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，记录结果
        if(root->left == nullptr && root->right == nullptr)
        {
            path = path << 1 | root->val;
            ret += path;
            path = path >> 1;

            // ret += path << 1 | root->val;

            return;
        }

        // 前序遍历位置
        path = path << 1 | root->val;

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path = path >> 1;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int pseudoPalindromicPaths (TreeNode* root) 
    {
        traverse(root);

        return res;
    }

    int count[10] = {0}; // 记录节点值每个数字的出现次数

    int res = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，记录结果
        if(root->left == nullptr && root->right == nullptr)
        {
            int odd = 0;

            count[root->val]++;

            for(int i = 0; i < 10; i++)
            {
                if(count[i] % 2)
                    odd++;
            }

            if(odd <= 1)
                res++;

            count[root->val]--;

            return;
        }

        // 前序遍历位置
        count[root->val]++;

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        count[root->val]--;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        traverse(root);

        return res;
    }

    // 递归遍历路径
    vector<string> path;

    // 记录结果
    vector<string> res;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，记录结果
        if(root->left == nullptr && root->right == nullptr)
        {
            path.push_back(to_string(root->val));
            res.push_back(join("->", path));
            path.pop_back();

            return;
        }

        // 前序遍历位置
        path.push_back(to_string(root->val));

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }

    string join(const string& sep, const vector<string>& path)
    {
        string ret = "";
        for(int i = 0; i < path.size(); i++)
        {
            ret += path[i];
            if(i < path.size() - 1)
                ret += sep;
        }

        return ret;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) 
    {
        traverse(root);

        return res;
    }

    // 记录递归函数路径上的数字
    string path = "";

    // 记录结果
    int res = 0; 

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 前序遍历位置
        path += to_string(root->val);

        // 到达叶子节点，累加结果
        if(root->left == nullptr && root->right == nullptr)
        {
            res += stoi(path);
        }

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) 
    {
        traverse(root);

        return res;
    }

    // 记录递归函数路径上的数字
    string path = "";

    // 记录结果
    int res = 0; 

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，累加结果
        if(root->left == nullptr && root->right == nullptr)
        {
            path += to_string(root->val);
            res += stoi(path);
            path.pop_back();
            return;
        }

        // 前序遍历位置
        path += to_string(root->val);

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    // 记录递归函数遍历的右侧节点
    vector<int> ret;

    // 记录递归遍历的层数
    int depth = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 前序遍历位置
        depth++;

        if(ret.size() < depth)// 说明这一层之前没有遍历到，因为先遍历右子树，所以这里的root节点就是右侧节点
        {
            ret.push_back(root->val);
        }

        traverse(root->right); // 注意顺序
        traverse(root->left);

        // 后序遍历位置
        depth--;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int longestConsecutive(TreeNode* root) 
    {
        traverse(root, 1, INT_MIN);

        return maxLen;
    }

    int maxLen = 0;

    void traverse(TreeNode* root, int len, int parentVal)
    {
        if(root == nullptr)
            return;

        if(root->val == parentVal + 1)
            len++;
        else
            len = 1;

        maxLen = max(maxLen, len);

        traverse(root->left, len, root->val);
        traverse(root->right, len, root->val);
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string smallestFromLeaf(TreeNode* root) 
    {
        traverse(root);

        return res;
    }

    // 递归遍历路径
    string path = "";

    // 结果字符串
    string res = "";

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，比较字符串
        if(root->left == nullptr && root->right == nullptr)
        {
            path += (char)('a' + root->val);
            // 反转字符串，比较
            reverse(path.begin(), path.end()); // algorithm
            if(res.empty() || res.compare(path) > 0)
                res = path;

            // 还原字符串
            reverse(path.begin(), path.end());

            path.pop_back();
        }

        // 前序遍历位置
        path += (char)('a' + root->val);

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    // 记录递归函数路径上的二进制数
    int path = 0;

    // 记录结果
    int ret = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点， 更新结果
        if(root->left == nullptr && root->right == nullptr)
        {
            path = path << 1 | root->val;
            ret += path;
            path = path >> 1;

            return;
        }

        // 前序遍历位置
        path = path << 1 | root->val;

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path = path >> 1;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int pseudoPalindromicPaths (TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    // 记录每个节点值的出现次数
    int count[10] = {0};

    int ret = 0; // 记录结果

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;


        // 到达叶子节点，更新结果
        if(root->left == nullptr && root->right == nullptr)
        {
            count[root->val]++;

            int num = 0;

            for(int i = 0; i < 10; i++)
            {
                if(count[i] % 2)
                    num++; // 奇数个数字不能超过一个，否组不满足条件
            }

            if(num <= 1)
                ret++;
            
            count[root->val]--;

            return;
        }

        // 前序遍历位置
        count[root->val]++;

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        count[root->val]--;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) 
    {
        if(root == nullptr)
            return nullptr;

        if(root->val < val)
            return searchBST(root->right, val);
        
        if(root->val > val)
            return searchBST(root->left, val);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) 
    {
        // 找左叶子节点，并累加即可
        traverse(root);

        return sum;
    }

    // 记录左叶子节点之和
    int sum = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 如何判断左叶子呢？ 注意了！！！
        if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr)
            sum += root->left->val;

        traverse(root->left);
        traverse(root->right);
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) 
    {
        if(root1 == nullptr)
            return root2;

        if(root2 == nullptr)
            return root1;

        // 两棵树都有的节点，相加
        root1->val += root2->val;

        // 递归合并左右子树
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);

        return root1;
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        traverse(root);

        return res;
    }

    // 记录递归函数的路径
    vector<string> path;

    // 记录结果
    vector<string> res;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，更新结果
        if(root->left == nullptr && root->right == nullptr)
        {
            path.push_back(to_string(root->val));
            res.push_back(join("->", path));
            path.pop_back();

            return;
        }

        // 前序遍历位置
        path.push_back(to_string(root->val));

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }

    string join(const string& sep, const vector<string>& path)
    {
        string ret = "";
        for(int i = 0; i < path.size(); i++)
        {
            ret += path[i];
            if(i < path.size() - 1)
                ret += sep;
        }

        return ret;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    // 记录递归函数经过的路径
    string path = "";

    // 记录结果
    int ret = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，更新结果
        if(root->left == nullptr && root->right == nullptr)
        {
            path += to_string(root->val);
            ret += stoi(path);
            path.pop_back();
            return;
        }

        // 前序遍历位置
        path += to_string(root->val);

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    // 记录递归函数经过的路径
    string path = "";

    // 记录结果
    int ret = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，更新结果
        if(root->left == nullptr && root->right == nullptr)
        {
            path += to_string(root->val);
            ret += stoi(path);
            path.pop_back();
            return;
        }

        // 前序遍历位置
        path += to_string(root->val);

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    // 记录结果
    vector<int> ret;

    // 记录递归函数的层数
    int depth = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        depth++;

        if(ret.size() < depth) // 说明这一层还没有记录值，此时该根节点就是最右侧节点
        {
            ret.push_back(root->val);
        }

        traverse(root->right);
        traverse(root->left);

        depth--;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int longestConsecutive(TreeNode* root) 
    {
        traverse(root, 0, root->val);

        return maxLen;
    }

    // 记录结果
    int maxLen = 1;

    void traverse(TreeNode* root, int len, int parentVal)
    {
        if(root == nullptr)
            return;

        if(root->val == parentVal + 1)
            len++;
        else
            len = 1;

        maxLen = max(maxLen, len);

        traverse(root->left, len, root->val);
        traverse(root->right, len, root->val);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string smallestFromLeaf(TreeNode* root) 
    {
        traverse(root);

        return res;
    }

    // 记录递归函数路径
    string path = "";

    // 记录结果
    string res = "";

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，比较
        if(root->left == nullptr && root->right == nullptr)
        {
            path += (char)('a' + root->val);
            reverse(path.begin(), path.end());
            if(res.empty() || res.compare(path) > 0)
                res = path;

            // 恢复字符串
            reverse(path.begin(), path.end());
            path.pop_back();
        }

        // 前序遍历位置
        path += (char)('a' + root->val);

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) 
    {
        traverse(root);

        return ret;
    }

    // 记录递归路径上的二进制数
    int path = 0;

    // 记录结果
    int ret = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，更新结果
        if(root->left == nullptr && root->right == nullptr)
        {
            path = path << 1 | root->val;
            ret += path;
            path = path >> 1;

            return;
        }

        // 前序遍历位置
        path = path << 1 | root->val;

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path = path >> 1;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int pseudoPalindromicPaths (TreeNode* root) 
    {
        if(root == nullptr)
            return 0;

        traverse(root);

        return ret;
    }

    // 记录二叉树节点值的出现次数
    int count[10] = {0};

    // 记录结果
    int ret = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 到达叶子节点，更新结果
        if(root->left == nullptr && root->right == nullptr)
        {
            int num = 0; // 统计奇数的出现次数

            count[root->val]++;

            for(int i = 0; i < 10; i++)
            {
                if(count[i] % 2)
                    num++;
            }

            if(num <= 1)
                ret++;

            count[root->val]--;

            return;
        }

        // 前序遍历位置
        count[root->val]++;

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        count[root->val]--;
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 记录中序序列值到索引的映射
    unordered_map<int, int> valToIndex; // 元素是无重复的

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        for(int i = 0; i < inorder.size(); i++)
        {
            valToIndex[inorder[i]] = i;
        }

        return build(preorder, 0, preorder.size() - 1, 
                     inorder, 0, inorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& inorder, int inStart, int inEnd)
    {
        if(preStart > preEnd)
            return nullptr;

        int rootVal = preorder[preStart];
        int index = valToIndex[rootVal];

        int leftSize = index - inStart; // 左子树的长度

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize, 
                           inorder, inStart, index - 1);

        root->right = build(preorder, preStart + leftSize + 1, preEnd, 
                            inorder, index + 1, inEnd);

        return root;
    }


};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 建立中序序列值到索引的映射
    unordered_map<int, int> valToIndex;

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        for(int i = 0; i < inorder.size(); i++)
        {
            valToIndex[inorder[i]] = i;
        }

        return build(inorder, 0, inorder.size() - 1, 
                     postorder, 0, postorder.size() - 1);
    }

    TreeNode* build(vector<int>& inorder, int inStart, int inEnd, 
                    vector<int>& postorder, int postStart, int postEnd)
    {
        if(inStart > inEnd)
            return nullptr;

        int rootVal = postorder[postEnd];
        int index = valToIndex[rootVal];

        int leftSize = index - inStart;

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(inorder, inStart, index - 1, 
                           postorder, postStart, postStart + leftSize - 1);

        root->right = build(inorder, index + 1, inEnd, 
                            postorder, postStart + leftSize, postEnd - 1);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) 
    {
        if(nums.empty())
            return nullptr;

        return build(nums, 0, nums.size() - 1);
    }

    // int rootVal = INT_MIN;
    // int index = -1;

    TreeNode* build(vector<int>& nums, int left, int right)
    {
        int rootVal = INT_MIN;
        int index = -1;

        if(left > right)
            return nullptr;

        for(int i = left; i <= right; i++)
        {
            if(nums[i] > rootVal)
            {
                rootVal = nums[i];
                index = i;
            }
        }

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(nums, left, index - 1);
        root->right = build(nums, index + 1, right);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 建立后序遍历值到索引的映射
    unordered_map<int, int> valToIndex;

    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) 
    {
        for(int i = 0; i < postorder.size(); i++)
            valToIndex[postorder[i]] = i;

        return build(preorder, 0, preorder.size() - 1, 
                     postorder, 0, postorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& postorder, int postStart, int postEnd)
    {
        if(preStart > preEnd)
            return nullptr;

        if(preStart == preEnd) // 防止后面求leftRootVal越界
            return new TreeNode(preorder[preStart]);

        int rootVal = preorder[preStart];
        int leftRootVal = preorder[preStart + 1];
        int index = valToIndex[leftRootVal];

        int leftSize = index - postStart + 1;

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize, 
                           postorder, postStart, index);
        root->right = build(preorder, preStart + leftSize + 1, preEnd, 
                            postorder, index + 1, postEnd - 1);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 建立中序序列值到索引的映射
    unordered_map<int, int> valToIndex;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        for(int i = 0; i < inorder.size(); i++)
        {
            valToIndex[inorder[i]] = i;
        }

        return build(preorder, 0, preorder.size() - 1, 
                     inorder, 0, inorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& inorder, int inStart, int inEnd)
    {
        if(preStart > preEnd)
            return nullptr;

        int rootVal = preorder[preStart];
        int index = valToIndex[rootVal];

        int leftSize = index - inStart;

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 构建左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize, 
                           inorder, inStart, index - 1);
        root->right = build(preorder, preStart + leftSize + 1, preEnd, 
                            inorder, index + 1, inEnd);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        // 方法二：递归分解子问题
        
        vector<int> ret; // 记录结果

        if(root == nullptr)
            return ret;

        ret.push_back(root->val);

        vector<int> leftNum = preorderTraversal(root->left);
        ret.insert(ret.end(), leftNum.begin(), leftNum.end());

        vector<int> rightNum = preorderTraversal(root->right);
        ret.insert(ret.end(), rightNum.begin(), rightNum.end());

        return ret;
    }

    // vector<int> preorderTraversal(TreeNode* root) 
    // {
    //     // 方法一：遍历二叉树
    //     traverse(root);

    //     return ret;
    // }

    // // 记录结果
    // vector<int> ret;

    // void traverse(TreeNode* root)
    // {
    //     if(root == nullptr)
    //         return;

    //     // 前序遍历位置
    //     ret.push_back(root->val);

    //     traverse(root->left);
    //     traverse(root->right);
    // }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    vector<int> inorderTraversal(TreeNode* root) 
    {
        // 解法二：递归分解：将原问题分解成规模更小但是结构相同的子问题
        vector<int> ret;

        if(root == nullptr)
            return ret;

        vector<int> leftNum = inorderTraversal(root->left);
        ret.insert(ret.end(), leftNum.begin(), leftNum.end());

        ret.push_back(root->val);

        vector<int> rightNum = inorderTraversal(root->right);
        ret.insert(ret.end(), rightNum.begin(), rightNum.end());

        return ret;

    }

    // vector<int> inorderTraversal(TreeNode* root) 
    // {
    //     // 解法一：遍历二叉树：每个节点在做什么？什么时候做？
    //     traverse(root);

    //     return ret;
    // }

    // vector<int> ret;

    // void traverse(TreeNode* root)
    // {
    //     if(root == nullptr)
    //         return;


    //     traverse(root->left);

    //     ret.push_back(root->val);

    //     traverse(root->right);
    // }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    vector<int> postorderTraversal(TreeNode* root) 
    {
        // 解法二：递归分解：将原问题分解成规模更小的子问题
        vector<int> ret;

        if(root == nullptr)
            return ret;

        vector<int> leftNum = postorderTraversal(root->left);
        ret.insert(ret.end(), leftNum.begin(), leftNum.end());

        vector<int> rightNum = postorderTraversal(root->right);
        ret.insert(ret.end(), rightNum.begin(), rightNum.end());

        ret.push_back(root->val);

        return ret;
    }


    // vector<int> postorderTraversal(TreeNode* root) 
    // {
    //     // 解法一：遍历二叉树 - 每个节点需要做什么？什么时候做？
    //     traverse(root);

    //     return ret;
    // }

    // vector<int> ret;

    // void traverse(TreeNode* root)
    // {
    //     if(root == nullptr)
    //         return;

    //     traverse(root->left);
    //     traverse(root->right);

    //     ret.push_back(root->val);
    // }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:

    vector<int> preorder(Node* root) 
    {
        // 解法二：递归分解子问题 - 将原问题分解成规模更小但是结构相同的子问题
        vector<int> ret;

        if(root == nullptr)
            return ret;

        ret.push_back(root->val);

        for(auto& child : root->children)
        {
            vector<int> num = preorder(child);
            ret.insert(ret.end(), num.begin(), num.end());
        }

        return ret;
    }

    // vector<int> preorder(Node* root) 
    // {
    //     // 解法一：遍历二叉树 - 每个节点需要做什么？什么时候做？

    //     traverse(root);

    //     return ret;    
    // }

    // vector<int> ret;

    // void traverse(Node* root)
    // {
    //     if(root == nullptr)
    //         return;

    //     ret.push_back(root->val);

    //     for(auto& child : root->children)
    //     {
    //         traverse(child);
    //     }
    // }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) 
    {
        traverse(root);

        return ret;
    }

    int ret = 0;

    int depth = 0;

    void traverse(Node* root)
    {
        if(root == nullptr)
            return;

        depth++;

        ret = max(ret, depth);

        for(auto& child : root->children)
        {
            traverse(child);
        }

        depth--;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) 
    {
        traverse(root);

        return ret;
    }

    int ret = 0;

    int depth = 0;

    void traverse(Node* root)
    {
        if(root == nullptr)
            return;

        depth++;

        ret = max(ret, depth);

        for(auto& child : root->children)
        {
            traverse(child);
        }

        depth--;
    }
};



/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:

    vector<int> postorder(Node* root) 
    {
        vector<int> ret;

        // 思路二：递归分解子问题 - 将原问题分解成规模更小但是结构相同的子问题
        if(root == nullptr)
            return ret;
        
        for(auto& child : root->children)
        {
            vector<int> num = postorder(child);
            ret.insert(ret.end(), num.begin(), num.end());
        }

        ret.push_back(root->val);

        return ret;
    }

    // vector<int> postorder(Node* root) 
    // {
    //     // 思路一：遍历二叉树-每个节点需要做什么？什么时候做（前中后序位置）？
    //     traverse(root);

    //     return ret;    
    // }

    // vector<int> ret;

    // void traverse(Node* root)
    // {
    //     if(root == nullptr)
    //         return;

    //     for(auto& child : root->children)
    //         traverse(child);

    //     ret.push_back(root->val);
    // }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    int maxDepth(TreeNode* root) 
    {
        // 思路二：递归分解子问题-将原问题分解成规模更小但是结构相同的子问题
        if(root == nullptr)
            return 0;

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        return max(leftDepth, rightDepth) + 1;
    }

    // int maxDepth(TreeNode* root) 
    // {
    //     // 思路一：遍历二叉树-每个节点需要做什么？什么时候做？
    //     traverse(root);

    //     return ret;
    // }

    // int ret = 0;
    // int depth = 0; // 遍历的节点所在的层数

    // void traverse(TreeNode* root)
    // {
    //     if(root == nullptr)
    //         return;

    //     depth++;

    //     ret = max(ret, depth);

    //     traverse(root->left);
    //     traverse(root->right);

    //     depth--;
    // }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:

    int maxDepth(Node* root) 
    {
        int ret = 0;
        // 思路二：递归分解子问题-将原问题分解成规模更小的子问题
        if(root == nullptr)
            return 0;

        for(auto& child : root->children)
        {
            int num = maxDepth(child);
            ret = max(num, ret);
        }

        return ret + 1;
    }

    // int maxDepth(Node* root) 
    // {
    //     // 思路一：遍历二叉树-每个节点需要做什么？什么时候做？
    //     traverse(root);

    //     return ret;    
    // }

    // int ret = 0;

    // int depth = 0; // 遍历到的节点所在的层数

    // void traverse(Node* root)
    // {
    //     if(root == nullptr)
    //         return;

    //     depth++;

    //     ret = max(ret, depth);

    //     for(auto& child : root->children)
    //         traverse(child);

    //     depth--;
    // }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) 
    {
        // 解法一：遍历二叉树-每个节点需要做什么？什么时候做？
        // traverse(root, targetSum);
        target = targetSum;
        traverse(root);

        return ret;
    }

    bool ret = false;
    int target = 0;
    int path = 0; // 遍历路径上的节点数值之和

    // void traverse(TreeNode* root, int targetSum)
    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 前序遍历位置
        path += root->val;

        if(root->left == nullptr && root->right == nullptr)
        {
            if(path == target)
                ret = true;
        }

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path -= root->val;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) 
    {
        // 解法一：遍历二叉树-每个节点需要做什么？什么时候做？
        // traverse(root, targetSum);
        target = targetSum;
        traverse(root);

        return ret;
    }

    bool ret = false;
    int target = 0;
    int path = 0; // 遍历路径上的节点数值之和

    // void traverse(TreeNode* root, int targetSum)
    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // // 前序遍历位置
        // path += root->val;

        // if(root->left == nullptr && root->right == nullptr)
        // {
        //     if(path == target)
        //         ret = true;
        // }

        if(root->left == nullptr && root->right == nullptr)
        {
            path += root->val;
            if(path == target)
                ret = true;

            path -= root->val;
            return;
        }

        // 前序遍历位置
        path += root->val;

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path -= root->val;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) 
    {
        if(root == nullptr)
            return false;

        if(root->left == nullptr && root->right == nullptr && root->val == targetSum)
            return true;

        return hasPathSum(root->left, targetSum - root->val) 
            || hasPathSum(root->right, targetSum - root->val);
    }

    // bool hasPathSum(TreeNode* root, int targetSum) 
    // {
    //     // 解法一：遍历二叉树-每个节点需要做什么？什么时候做？
    //     // traverse(root, targetSum);
    //     target = targetSum;
    //     traverse(root);

    //     return ret;
    // }

    // bool ret = false;
    // int target = 0;
    // int path = 0; // 遍历路径上的节点数值之和

    // // void traverse(TreeNode* root, int targetSum)
    // void traverse(TreeNode* root)
    // {
    //     if(root == nullptr)
    //         return;

    //     // // 前序遍历位置
    //     // path += root->val;

    //     // if(root->left == nullptr && root->right == nullptr)
    //     // {
    //     //     if(path == target)
    //     //         ret = true;
    //     // }

    //     if(root->left == nullptr && root->right == nullptr)
    //     {
    //         path += root->val;
    //         if(path == target)
    //             ret = true;

    //         path -= root->val;
    //         return;
    //     }

    //     // 前序遍历位置
    //     path += root->val;

    //     traverse(root->left);
    //     traverse(root->right);

    //     // 后序遍历位置
    //     path -= root->val;
    // }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) 
    {
        target = targetSum;

        traverse(root);

        return ret;
    }

    vector<vector<int>> ret; // 记录结果

    vector<int> path; // 记录遍历的路径

    int target = 0;

    void traverse(TreeNode* root)
    {
        int count = 0;

        if(root == nullptr)
            return;

        if(root->left == nullptr && root->right == nullptr)
        {
            path.push_back(root->val);
            for(int i = 0; i < path.size(); i++)
            {
                count += path[i];
            }
            if(count == target)
                ret.push_back(path);

            path.pop_back();

            return;
        }

        // 前序遍历位置
        path.push_back(root->val);

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        path.pop_back();
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        traverse(root);

        return root;
    }

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;

        traverse(root->left);
        traverse(root->right);
    }


    // TreeNode* invertTree(TreeNode* root) 
    // {
    //     // 解法一：分解子问题-将原问题分解成规模更小的子问题
    //     if(root == nullptr)
    //         return nullptr;

    //     TreeNode* left = invertTree(root->left);
    //     TreeNode* right = invertTree(root->right);

    //     root->left = right;
    //     root->right = left;

    //     return root;
    // }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    int sumOfLeftLeaves(TreeNode* root) 
    {
        int sum = 0;

        if(root == nullptr)
            return 0;

        if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr)
            sum += root->left->val;

        sum += sumOfLeftLeaves(root->left);
        sum += sumOfLeftLeaves(root->right);

        return sum;
    }

    // int sumOfLeftLeaves(TreeNode* root) 
    // {
    //     // 解法一：遍历二叉树-每个节点需要做什么？什么时候做？
    //     traverse(root);

    //     return sum;
    // }

    // int sum = 0;

    // void traverse(TreeNode* root)
    // {
    //     if(root == nullptr)
    //         return;

    //     // 如何找到左叶子？
    //     if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr)
    //         sum += root->left->val;

    //     traverse(root->left);
    //     traverse(root->right);
    // }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) 
    {
        if(root == nullptr)
        {
            return subRoot == nullptr;
        }

        if(isSametree(root, subRoot))
            return true;

        return isSubtree(root->left, subRoot) 
            || isSubtree(root->right, subRoot);
    }

    bool isSametree(TreeNode* p, TreeNode* q)
    {
        if(p == nullptr && q == nullptr)
            return true;
        
        if(p == nullptr || q == nullptr)
            return false;
        
        if(p->val != q->val)
            return false;

        return isSametree(p->left, q->left) && isSametree(p->right, q->right);
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) 
    {
        // base case
        if(head == nullptr) return true;
        if(root == nullptr) return false;

        if(head->val == root->val)
        {
            // 判断是否可以将链表嵌入到二叉树里面
            if(check(head, root))
                return true;
        }

        return isSubPath(head, root->left)
            || isSubPath(head, root->right);
    }

    bool check(ListNode* head, TreeNode* root)
    {
        if(head == nullptr) return true;
        if(root == nullptr) return false;

        if(head->val == root->val)
            return check(head->next, root->left) 
            || check(head->next, root->right);

        return false;
    }
};



/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/

class Solution {
public:
    Node* treeToDoublyList(Node* root) 
    {
        // 先把左右子树都变成环形链表
        // 根节点接到左右两个环形链表中间
        // 两个环形链表头尾相接形成大的环形链表

        if(root == nullptr)
            return nullptr;

        // 先把左右子树都变成环形链表
        Node* leftHead = treeToDoublyList(root->left);
        Node* rightHead = treeToDoublyList(root->right);
        Node* leftTail = nullptr, *rightTail = nullptr;   

        // 根节点接到左右两个环形链表中间
        if(leftHead != nullptr)
        {
            leftTail = leftHead->left;
            root->left = leftTail;
            leftTail->right = root;
        } 
        else
        {
            leftHead = leftTail = root;
        }

        if(rightHead != nullptr)
        {
            rightTail = rightHead->left;
            root->right = rightHead;
            rightHead->left = root;
        }
        else
        {
            rightHead = rightTail = root;
        }

        // 两个环形链表头尾相连形成更大的环形链表
        leftHead->left = rightTail;
        rightTail->right = leftHead;

        return leftHead;
    }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) 
    {
        if(root == nullptr)
            return nullptr;

        // 将左右子树转化成双向链表
        Node* leftHead = treeToDoublyList(root->left);
        Node* rightHead = treeToDoublyList(root->right);
        Node* leftTail = nullptr;
        Node* rightTail = nullptr;

        // 将根节点放到两条链表之间
        if(leftHead != nullptr)
        {
            leftTail = leftHead->left;
            root->left = leftTail;
            leftTail->right = root;
        }    
        else
        {
            leftHead = leftTail = root;
        }

        if(rightHead != nullptr)
        {
            rightTail = rightHead->left;
            root->right = rightHead;
            rightHead->left = root;
        }
        else
        {
            rightHead = rightTail = root;
        }

        // 将两条链表合并成更大的链表
        leftHead->left = rightTail;
        rightTail->right = leftHead;

        return leftHead;
    }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) 
    {
        if(root == nullptr)
            return nullptr;

        // 先将左右子树转换成循环链表
        Node* leftHead = treeToDoublyList(root->left);
        Node* rightHead = treeToDoublyList(root->right);
        Node* leftTail = nullptr, *rightTail = nullptr;

        // 将根节点插入到左右子树转化成的链表之间
        if(leftHead != nullptr)
        {
            leftTail = leftHead->left;
            root->left = leftTail;
            leftTail->right = root;
        }
        else
        {
            leftHead = leftTail = root;
        }

        if(rightHead != nullptr)
        {
            rightTail = rightHead->left;
            root->right = rightHead;
            rightHead->left = root;
        }
        else
        {
            rightHead = rightTail = root;
        }

        // 合并两个链表成为一个大的链表
        leftHead->left = rightTail;
        rightTail->right = leftHead;

        return leftHead;
            
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int n) 
    {
        if(n % 2 == 0) // 偶数个节点，一定不满足满二叉树的性质
            return {};

        return build(n);
    }

    // 输入一个数n, 生成节点数为n的所有满二叉树
    vector<TreeNode*> build(int n)
    {
        vector<TreeNode*> ret;

        // base case
        if(n == 1)
            ret.push_back(new TreeNode(0));

        for(int i = 1; i < n; i += 2)
        {
            int j = n - i - 1;

            vector<TreeNode*> leftSubTrees = build(i);
            vector<TreeNode*> rightSubTrees = build(j);

            // 将左右子树调换顺序，又变成了新的二叉树
            for(TreeNode* left : leftSubTrees)
            {
                for(TreeNode* right : rightSubTrees)
                {
                    // 构造根节点
                    TreeNode* root = new TreeNode(0);

                    ret.push_back(root);

                    root->left = right;
                    root->right = left;
                }
            }
        }

        return ret;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) 
    {
        if(root == nullptr)
            return new TreeNode(val);

        if(root->val < val)
        {
            TreeNode* temp = new TreeNode(val);
            temp->left = root;
            root = temp;
        }
        else
        {
            root->right = insertIntoMaxTree(root->right, val);
        }

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) 
    {
        if(root == nullptr)
            return {};

        for(int d : to_delete)
            delNums.insert(d);

        doDelete(root, false);

        return ret;
    }

    // 记录需要删除的节点
    unordered_set<int> delNums;

    // 记录森林的根
    vector<TreeNode*> ret;

    TreeNode* doDelete(TreeNode* root, bool hasParent)
    {
        if(root == nullptr)
            return nullptr;

        bool deleted = delNums.count(root->val);

        if(!deleted && !hasParent)
            ret.push_back(root);

        root->left = doDelete(root->left, !deleted);
        root->right = doDelete(root->right, !deleted);

        return !deleted ? root : nullptr;
    }
};


/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     Node *left;
 *     Node *right;
 *     Node *random;
 *     Node() : val(0), left(nullptr), right(nullptr), random(nullptr) {}
 *     Node(int x) : val(x), left(nullptr), right(nullptr), random(nullptr) {}
 *     Node(int x, Node *left, Node *right, Node *random) : val(x), left(left), right(right), random(random) {}
 * };
 */

class Solution {
public:
    // 建立原始节点到复制节点的映射
    unordered_map<Node*, NodeCopy*> nodeToCopy;

    NodeCopy* copyRandomBinaryTree(Node* root) 
    {
        if(root == nullptr)
            return nullptr;

        if(nodeToCopy.count(root))
            return nodeToCopy[root];

        NodeCopy* copy = new NodeCopy(root->val);
        nodeToCopy[root] = copy;

        copy->left = copyRandomBinaryTree(root->left);
        copy->right = copyRandomBinaryTree(root->right);
        copy->random = copyRandomBinaryTree(root->random);

        return copy;
    }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    Node* cloneTree(Node* root) 
    {
        if(root == nullptr)
            return nullptr;

        Node* cpRoot = new Node(root->val);

        for(Node* child : root->children)
        {
            cpRoot->children.push_back(cloneTree(child));
        }       

        return cpRoot;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    // 记录已经访问过的节点
    unordered_set<TreeNode*> visited;

public:
    TreeNode* correctBinaryTree(TreeNode* root) 
    {
        if(root == nullptr)
            return nullptr;

        if(root->right != nullptr && visited.count(root->right))
        {
            // 找到无效节点, 直接删除
            return nullptr;
        }

        visited.insert(root);

        root->right = correctBinaryTree(root->right); // 注意递归的先后顺序
        root->left = correctBinaryTree(root->left);

        return root;
    }
};


class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        // 建立值到索引的映射
        unordered_map<int, int> valToIndex;    

        for(int i = 0; i < nums.size(); i++)
        {
            int need = target - nums[i];
            if(valToIndex.count(need))
            {
                return {valToIndex[need], i};
            }

            valToIndex[nums[i]] = i;
        }

        return {-1, -1};
    }

};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        if(root == nullptr)
            return true;

        return check(root->left, root->right);
    }

    bool check(TreeNode* left, TreeNode* right)
    {
        if(left == nullptr || right == nullptr)
            return left == right;

        if(left->val != right->val)
            return false;

        return check(left->right, right->left)
            && check(left->left, right->right);
    }
};



// 二叉树的最大深度
// 方法一：遍历二叉树求得答案-用外部变量记录每个节点的深度，取最大值即可

int res = 0; // 记录最大深度

int depth = 0; // 记录遍历到的节点的深度

// 主函数
int maxDepth(TreeNode* root)
{
        traverse(root);


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        if(root == nullptr)
            return true;

        return check(root->left, root->right);
    }

    bool check(TreeNode* left, TreeNode* right)
    {
        if(left == nullptr || right == nullptr)
            return left == right;

        if(left->val != right->val)
            return false;
        
        return check(left->right, right->left)
            && check(left->left, right->right);
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) 
    {
        if(nums.empty())
            return nullptr;

        return build(nums, 0, nums.size() - 1);
    }

    TreeNode* build(vector<int>& nums, int left, int right)
    {
        if(left > right)
            return nullptr;

        int maxNum = INT_MIN;
        int index = -1;

        for(int i = left; i <= right; i++)
        {
            if(maxNum < nums[i])
            {
                maxNum = nums[i];
                index = i;
            }
        }

        // 构建根节点
        TreeNode* root = new TreeNode(maxNum);

        // 递归构建左右子树
        root->left = build(nums, left, index - 1);
        root->right = build(nums, index + 1, right);

        return root;
        
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    // 建立中序序列值到索引的映射
    unordered_map<int, int> valToIndex;

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        for(int i = 0; i < inorder.size(); i++)
        {
            valToIndex[inorder[i]] = i;
        }

        return build(preorder, 0, preorder.size() - 1, 
                     inorder, 0, inorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& inorder, int inStart, int inEnd)
    {
        if(preStart > preEnd)
            return nullptr;

        int rootVal = preorder[preStart];
        int index = valToIndex[rootVal];

        int leftSize = index - inStart; // 左子树长度

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 递归构建左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize, 
                       inorder, inStart, index - 1);

        root->right = build(preorder, preStart + leftSize + 1, preEnd, 
                            inorder, index + 1, inEnd);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    // 建立后序序列值到索引的映射
    unordered_map<int, int> valToIndex;

public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) 
    {
        for(int i = 0; i < postorder.size(); i++)
        {
            valToIndex[postorder[i]] = i;
        }

        return build(preorder, 0, preorder.size() - 1, 
                     postorder, 0, postorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& postorder, int postStart, int postEnd)
    {
        if(preStart > preEnd)
            return nullptr;

        if(preStart == preEnd)
            return new TreeNode(preorder[preStart]); // 别忘记了这一步

        int rootVal = preorder[preStart];
        int leftRootVal = preorder[preStart + 1];
        int index = valToIndex[leftRootVal];

        int leftSize = index - postStart + 1; // 左子树大小

        // 构建根节点
        TreeNode* root = new TreeNode(rootVal);

        // 递归构建左右子树
        root->left = build(preorder, preStart + 1, preStart + leftSize, 
                           postorder, postStart, index);
        root->right = build(preorder, preStart + leftSize + 1, preEnd, 
                            postorder, index + 1, postEnd - 1);

        return root;

    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) 
    {
        if(root == nullptr)
            return new TreeNode(val);

        if(root->val < val)
        {
            TreeNode* temp = new TreeNode(val);
            temp->left = root;
            root = temp;
        }
        else
        {
            // 根据 最大二叉树 ，由于val值在末尾，所以构建二叉树时一定是位于右子树中的
            root->right = insertIntoMaxTree(root->right, val);
        }

        return root;
    }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/

class Solution {
public:
    Node* treeToDoublyList(Node* root) 
    {
        if(root == nullptr)
            return nullptr;

        // 递归转换左右子树
        Node* leftHead = treeToDoublyList(root->left); 
        Node* rightHead = treeToDoublyList(root->right); 
        Node* leftTail = nullptr;
        Node* rightTail = nullptr;

        // 将根节点放到左右子树转换的链表中间
        if(leftHead != nullptr)
        {
            leftTail = leftHead->left;
            root->left = leftTail;
            leftTail->right = root;
        }
        else
        {
            leftHead = leftTail = root;
        }

        if(rightHead != nullptr)
        {
            rightTail = rightHead->left;
            root->right = rightHead;
            rightHead->left = root;
        }
        else
        {
            rightHead = rightTail = root;
        }

        // 连接左右链表成为更大的链表
        leftHead->left = rightTail;
        rightTail->right = leftHead;

        return leftHead;

    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int n) 
    {
        if(n % 2 == 0)
            return {};

        return build(n);
    }

    // 输入一个数n, 构建节点数为n的所有满二叉树   
    vector<TreeNode*> build(int n)
    {
        vector<TreeNode*> ret;

        if(n == 1)
        {
            ret.push_back(new TreeNode(0));
            return ret;
        }

        for(int i = 1; i < n; i += 2)
        {
            int j = n - i - 1; // 节点总数-左子树-1

            vector<TreeNode*> leftNums = build(i);
            vector<TreeNode*> rightNums = build(j);

            // 交换左右子树又变成了新的二叉树
            for(TreeNode* left : leftNums)
            {
                for(TreeNode* right : rightNums)
                {
                    TreeNode* root = new TreeNode(0);

                    root->left = right;
                    root->right = left;

                    ret.push_back(root);
                }
            }
        }

        return ret;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) 
    {
        if(root == nullptr)
            return ret;

        for(int d : to_delete)
            delNums.insert(d);

        doDelete(root, false);

        return ret;
    }

    // 记录需要删除的节点
    unordered_set<int> delNums;

    // 记录森林的根
    vector<TreeNode*> ret;

    // 是否需要删除，必须得给父节点反馈让父节点知道
    TreeNode* doDelete(TreeNode* root, bool hasParent)
    {
        if(root == nullptr)
            return nullptr;

        bool deleted = delNums.count(root->val);

        if(!deleted && !hasParent)
            ret.push_back(root);

        // 递归遍历左右子树，判断是否需要删除
        root->left = doDelete(root->left, !deleted);
        root->right = doDelete(root->right, !deleted);

        return !deleted ? root : nullptr;
    }
};


// 二叉树层序遍历和BFS算法框架：
Queue<TreeNode> q = new LinkedList<>();

q.offer(root);

while(!q.empty()) // while循环控制每一层，一层一层往下遍历
{
	int sz = q.size();
	
	// for循环控制每一层中的每一个节点
	for(int i = 0; i < sz; i++)
	{
		TreeNode cur = q.poll();
		if(cur->left != nullptr)
			q.offer(cur->left);

		if(cur->right != nullptr)
			q.offer(cur->right);

	}
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> ret; // 记录结果
        if(root == nullptr)
            return ret;

        queue<TreeNode*> q;
        q.push(root);

        // while循环控制从上到下一层层遍历
        while(!q.empty())
        {
            int sz = q.size();
            vector<int> level; // 记录这一层节点值
            // for循环控制每一层从左向右遍历
            for(int i = 0; i < sz; i++)
            {
                TreeNode* cur = q.front();
                q.pop();
                level.push_back(cur->val);

                if(cur->left != nullptr)
                    q.push(cur->left);
                if(cur->right != nullptr)
                    q.push(cur->right);
            }
            // for循环结束说明这一层遍历完了，记录
            ret.push_back(level);
        }

        return ret;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> ret; // 记录结果

        if(root == nullptr)
            return ret;

        queue<TreeNode*> q;

        q.push(root);

        // while循环控制从上到下一层层遍历
        while(!q.empty())
        {
            vector<int> level; // 记录每一层的节点
            int sz = q.size();
            // for循环控制每一层从左向右遍历
            for(int i = 0; i < sz; i++)
            {
                TreeNode* cur = q.front();
                q.pop();
                level.push_back(cur->val);

                if(cur->left != nullptr)
                    q.push(cur->left);

                if(cur->right != nullptr)
                    q.push(cur->right);
            }

            // for 循环结束说明这一层遍历完了，记录
            ret.push_back(level);
        }

        return ret;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) 
    {
        vector<vector<int>> ret; // 记录结果

        if(root == nullptr)
            return ret;

        queue<TreeNode*> q;

        q.push(root);

        // while循环控制每一层从上到下遍历
        while(!q.empty())
        {
            int sz = q.size();
            vector<int> level; // 记录这一层的节点

            // for循环控制一层从左向右遍历
            for(int i = 0; i < sz; i++)
            {
                TreeNode* cur = q.front();
                q.pop();
                level.push_back(cur->val);

                if(cur->left != nullptr)
                    q.push(cur->left);

                if(cur->right != nullptr)
                    q.push(cur->right);
            }
            // 把每一层添加到头部，这就是从底向上遍历了
            ret.insert(ret.begin(), level);
        }

        return ret;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) 
    {
        if(root == nullptr)
            return {};

        vector<int> ret; // 记录结果

        queue<TreeNode*> q;
        q.push(root);

        // while循环控制每一层从上到下遍历
        while(!q.empty())
        {
            int sz = q.size();
            int maxVal = INT_MIN; // 记录每一层的最大值

            // for循环控制每一层从左向右遍历
            for(int i = 0; i < sz; i++)
            {
                TreeNode* cur = q.front();
                q.pop();
                // if(cur->val > maxVal)
                //     maxVal = cur->val;
                maxVal = max(maxVal, cur->val);

                if(cur->left != nullptr)
                    q.push(cur->left);

                if(cur->right != nullptr)
                    q.push(cur->right);
            }

            ret.push_back(maxVal);
        }

        return ret;
    }

    // vector<int> largestValues(TreeNode* root) {
    //     if (!root) {
    //         return {};
    //     }
    //     vector<int> res;
    //     queue<TreeNode*> q;
    //     q.push(root);
    //     while (!q.empty()) {
    //         int len = q.size();
    //         int maxVal = INT_MIN;
    //         while (len > 0) {
    //             len--;
    //             auto t = q.front();
    //             q.pop();
    //             maxVal = max(maxVal, t->val);
    //             if (t->left) {
    //                 q.push(t->left);
    //             }
    //             if (t->right) {
    //                 q.push(t->right);
    //             }
    //         }
    //         res.push_back(maxVal);
    //     }
    //     return res;
    // }


};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) 
    {
        if(root == nullptr)
            return {};

        vector<double> average;

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty())
        {
            double sum = 0.0;
            int sz = q.size();

            for(int i = 0; i < sz; i++)
            {
                TreeNode* cur = q.front();
                q.pop();
                sum += cur->val;

                if(cur->left != nullptr)
                    q.push(cur->left);

                if(cur->right != nullptr)
                    q.push(cur->right);
            }

            average.push_back(sum / sz);
        }

        return average;
    }
};


// 二叉树的锯齿形层序遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        if(root == nullptr)
            return {};

        vector<vector<int>> ret; // 记录结果

        queue<TreeNode*> q;
        q.push(root);

        // 记录层数
        int count = 0;

        while(!q.empty())
        {
            count++;
            int sz = q.size();
            list<int> level; //记录每一层的节点

            for(int i = 0; i < sz; i++)
            {
                TreeNode* cur = q.front();
                q.pop();

                if(count % 2) // 奇数
                {
                    level.push_back(cur->val);
                }
                else
                {
                    level.push_front(cur->val);
                }
                if(cur->left != nullptr)
                        q.push(cur->left);
                if(cur->right != nullptr)
                    q.push(cur->right);
            }

            ret.emplace_back(level.begin(), level.end()); // c++11-移动
        }
        return ret;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        if(root == nullptr)
            return {};

        vector<vector<int>> ret;

        queue<TreeNode*> q;

        q.push(root);

        bool flag = true; // flag为true时，从左向右，反之，从右向左

        while(!q.empty())
        {
            int sz = q.size();
            list<int> level;
            for(int i = 0; i < sz; i++)
            {
                TreeNode* cur = q.front();
                q.pop();
                if(flag)
                    level.push_back(cur->val);
                else
                    level.push_front(cur->val);

                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
            }

            ret.emplace_back(level.begin(), level.end());
            flag = !flag;
        }

        return ret;

    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCompleteTree(TreeNode* root) 
    {
        queue<TreeNode*> q;
        q.push(root);

        bool flag = false;

        while(!q.empty())
        {
            TreeNode* node = q.front();
            q.pop();

            if(node == nullptr)
            {
                flag = true;
                continue; // 跳出本轮循环之后进入下次循环，又遇到NULL说明不满序条件
            }

            if(flag != false) 
                return false;
            
            q.push(node->left);
            q.push(node->right);
            
        }
        return true;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 分别记录两个被错误的交换的节点
    TreeNode* first = nullptr, *second = nullptr;

    // 验证中序序列的有序性
    TreeNode* prev = new TreeNode(INT_MIN);

    void recoverTree(TreeNode* root) 
    {
        inorderTraverse(root);

        int temp = first->val;
        first->val = second->val;
        second->val = temp;

    }

    void inorderTraverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        inorderTraverse(root->left);

        // 中序遍历位置

        if(root->val < prev->val)
        {
            // 此时中序序列不是有序的
            if(first == nullptr)
                first = prev;

            second = root;
        }
        prev = root;

        inorderTraverse(root->right);
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) 
    {
        if(root == nullptr)
            return nullptr;

        TreeNode* successor = nullptr;

        if(root->val > p->val)
        {
            successor = inorderSuccessor(root->left, p);
            if(successor == nullptr)
                successor = root;
        }   

        if(root->val < p->val)
        {
            successor = inorderSuccessor(root->right, p);
        }

        if(root->val == p->val)
        {
            successor = getMin(root->right);
        }

        return successor;
    }

    // 找最小节点
    TreeNode* getMin(TreeNode* p)
    {
        while(p != nullptr && p->left != nullptr)
        {
            p = p->left;
        }

        return p;
    }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
public:
    Node* inorderSuccessor(Node* node) 
    {
        if(node == nullptr)
            return nullptr;

        // 右子树的最小值就是successor
        Node* p = node->right;
        while(p != nullptr && p->left != nullptr)
            p = p->left;

        if(p != nullptr)
            return p;

        // 没有右子树的话就去找它的父节点
        p = node;

        while(p->parent != nullptr && p->parent->right == p)
        {
            p = p->parent;
        }

        return p->parent;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    int depth = 0;
    int ret = 0;

    int maxDepth(TreeNode* root) 
    {
        // if(root == nullptr)
        //     return 0;

        // int leftDepth = maxDepth(root->left);
        // int rightDepth = maxDepth(root->right);

        // return max(leftDepth, rightDepth) + 1;

        // 回溯
        traverse(root);
        return ret;
    }

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 前序遍历位置
        depth++;

        // 遍历的过程中记录最大深度
        ret = max(ret, depth);

        traverse(root->left);
        traverse(root->right);

        // 后序遍历位置
        depth--;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    vector<int> res;

    vector<int> preorderTraversal(TreeNode* root) 
    {
        // vector<int> ret;

        // if(root == nullptr)
        //     return ret;

        // ret.push_back(root->val);

        // vector<int> leftNums = preorderTraversal(root->left);
        // ret.insert(ret.end(), leftNums.begin(), leftNums.end());

        // vector<int> rightNums = preorderTraversal(root->right);
        // ret.insert(ret.end(), rightNums.begin(), rightNums.end());

        // return ret;

        // 回溯
        traverse(root);

        return res;
    }

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 前序遍历位置
        res.push_back(root->val);

        traverse(root->left);
        traverse(root->right);
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) 
    {
        // 二叉树直径 - 一个节点左右子树最大深度之和
        maxDepth(root);

        return maxDiameter;
    }

private:
    int maxDiameter = 0;

    int maxDepth(TreeNode* root)
    {
        if(root == nullptr)
            return 0;

        int left = maxDepth(root->left);
        int right = maxDepth(root->right);

        // 后序遍历位置
        int myDiameter = left + right;

        maxDiameter = max(maxDiameter, myDiameter);

        return max(left, right) + 1;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        // if(root == nullptr)
        //     return 0;

        // int leftDepth = maxDepth(root->left);
        // int rightDepth = maxDepth(root->right);

        // return max(leftDepth, rightDepth) + 1;

        // 回溯
        traverse(root);

        return res;

    }

    int depth = 0;

    int res = 0;

    void traverse(TreeNode* root)
    {
        if(root == nullptr)
            return;

        // 前序遍历位置
        depth++;

        res = max(res, depth);

        traverse(root->left);
        traverse(root->right);

        depth--;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) 
    {
        // traverse(head);

        // return res;

        if(head == nullptr)
            return {};

        vector<int> subNums = reversePrint(head->next);

        subNums.push_back(head->val);

        return subNums;
    }

    // vector<int> res;
    // int len = 0; // 链表的长度
    // int p = 0; // 结果数组的位置

    // void traverse(ListNode* head)
    // {
    //     if(head == nullptr)
    //     {
    //         res.resize(len);
    //         return;
    //     }

    //     // 前序遍历位置
    //     len++;

    //     traverse(head->next);

    //     // 后序遍历位置
    //     res[p] = head->val;

    //     p++;
    // }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) 
    {
        // base case
        if(A == nullptr || B == nullptr)
            return false;

        // A->val == B->val 
        if(A->val == B->val && compareStructure(A, B))
            return true;
        else
            return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }

    bool compareStructure(TreeNode* A, TreeNode* B)
    {
        // base case
        if(B == nullptr) // 遍历到底了
            return true;

        if(B != nullptr && A == nullptr)
            return false;

        if(A->val != B->val)
            return false;

        return compareStructure(A->left, B->left) && compareStructure(A->right, B->right);
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) 
    {
        // base case
        if(A == nullptr || B == nullptr)
            return false;

        if(A->val == B->val && compareTree(A, B))
            return true;
        else
            return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }

    bool compareTree(TreeNode* rootA, TreeNode* rootB)
    {
        // base case
        if(rootB == nullptr) // 遍历到底了
            return true;

        if(rootA == nullptr && rootB != nullptr)
            return false;

        if(rootA->val != rootB->val)
            return false;

        return compareTree(rootA->left, rootB->left) &&
               compareTree(rootA->right, rootB->right);
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) 
    {
        // traverse(root);

        // return root;

        if(root == nullptr)
            return nullptr;

        // 利用函数定义，先反转左右子树
        TreeNode* left = mirrorTree(root->left);
        TreeNode* right = mirrorTree(root->right);

        // 交换左右子树
        root->left = right;
        root->right = left;

        return root;
    }

    // void traverse(TreeNode* root)
    // {
    //     if(root == nullptr)
    //         return;

    //     // 前序遍历位置
    //     // 每一个节点需要做的事很简单-交换它的左右节点
    //     TreeNode* tmp = root->left;
    //     root->left = root->right;
    //     root->right = tmp;

    //     traverse(root->left);
    //     traverse(root->right);
    // }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        // base case
        if(root == nullptr)
            return true;

        return check(root->left, root->right);
    }

    bool check(TreeNode* left, TreeNode* right)
    {
        // base case
        if(left == nullptr || right == nullptr)
            return left == right;

        if(left->val != right->val)
            return false;

        return check(left->right, right->left) &&
               check(left->left, right->right);
    }
};


// 二叉树的思维模式分为两类：
1. 是否可以通过遍历一遍二叉树得到答案？如果可以，用一个traverse函数配合外部变量来实现，这叫做「遍历」的思维模式；

2. 是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写一个递归函数的的定义，并充分利用这个函数的返回值，这叫做「分解问题」的思维模式。

无论哪种思维模式，我们都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么位置做？（前序/中序/后序位置），其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。


// 二叉树的遍历框架：

void traverse(TreeNode root)
{
	if(root == nullptr)
		return;

	// 前序遍历位置
	traverse(root->left);

	// 中序遍历位置
	
	traverse(root->right);

	// 后续遍历位置
}


前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点：

1. 前序位置的代码在刚刚进入一个二叉树节点的时候执行；

2. 后序位置的代码在即将离开一个二叉树节点的时候执行；

3. 中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候进行。


二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会在所有节点上做相同的操作。



二叉树解题的思维模式分为两类：

1. 是否可以通过遍历一遍二叉树得到答案？如果可以，用一个traverse函数配合外部变量来实现，这叫「遍历」的思维模式；

2. 是否可以定义一个递归函数，通过子问题（子树）的答案推导出愿问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫做「分解问题」的思维模式。

无论哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

二叉树的构造问题一般都是使用「分解问题」的思路：

构造整棵树 = 根节点 + 构造左子树 + 构造右子树。


前序位置的代码只能从函数参数中获取父节点传递过来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。
换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) 
    {
        if(root == nullptr)
            return;
        // 根据函数定义，将二叉树展开成为链表，可以先把左右子树展开成为链表，然后左子树作为右子树，原右子树接到现在右子树的末尾
        flatten(root->left);
        flatten(root->right);

        TreeNode* left = root->left;
        TreeNode* right = root->right;

        root->left = nullptr;
        root->right = left;

        TreeNode* p = root;

        while(p->right != nullptr)
        {
            p = p->right;
        }

        p->right = right;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) 
    {
        if(root == nullptr)
            return nullptr;
            
        // 将原二叉树的每个相邻节点视为三叉树的一个节点
        traverse(root->left, root->right);

        return root;    
    }

    void traverse(Node* node1, Node* node2)
    {
        if(node1 == nullptr || node2 == nullptr)
            return;

        node1->next = node2;

        traverse(node1->left, node1->right);
        traverse(node2->left, node2->right);

        traverse(node1->right, node2->left);
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& inorder, int inStart, int inEnd)
    {
        if(preStart > preEnd)
        {
            return nullptr;
        }

        int rootVal = preorder[preStart];

        int index = -1;
        for(int i = inStart; i <= inEnd; i++)
        {
            if(inorder[i] == rootVal)
            {
                index = i;
            }
        }

        int leftSize = index - inStart;

        TreeNode* root = new TreeNode(rootVal);

        root->left = build(preorder, preStart + 1, preStart + leftSize, 
                           inorder, inStart, index - 1);

        root->right = build(preorder, preStart + leftSize + 1, preEnd, 
                            inorder, index + 1, inEnd);

        return root;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    string NULL_STR = "#";
    string SEP = ",";

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) 
    {
        // 将二叉树序列化成为字符串
        if(root == nullptr)
        {
            return NULL_STR + SEP;
        }

        string res = to_string(root->val) + SEP;

        res += serialize(root->left);
        res += serialize(root->right);

        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) 
    {
        // 反序列化，先将字符串转换成为列表，然后再将列表反序列化成二叉树
        list<string> dataArray;
        stringstream ss(data); // 用于拼接字符串

        string str;

        while(getline(ss, str, ','))
        {
            dataArray.push_back(str);
        }

        return deserialize(dataArray);
    }

    TreeNode* deserialize(list<string>& dataArray)
    {
        if(dataArray.front() == NULL_STR)
        {
            dataArray.erase(dataArray.begin());
            return nullptr;
        }

        TreeNode* root = new TreeNode(stoi(dataArray.front()));
        dataArray.erase(dataArray.begin());

        root->left = deserialize(dataArray);
        root->right = deserialize(dataArray);

        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));


BST的特性：

1. 对于BST的每一个节点node，左子树节点的值都比node的值要小，右节点的值都比node值要大；

2. 对于BST的每一个节点node，它的左侧子树和右侧子树都是BST。

BST的中序遍历结果是有序的，升序排列


